package fun.stgoder.test1.source;

public class TestHashMapSource {
    public static void main(String[] args) {

        /*HashMap<String, String> map = new HashMap<>();

        map.put("k1", "v1");


        String v1 = map.get("k1");
        System.out.println(v1);*/


        SimpleHashMap<String, String> simpleHashMap = new SimpleHashMap<>();

        for (int i = 0; i < 20; i++) {
            simpleHashMap.put("k" + i, "v" + i);
        }

        String v10 = simpleHashMap.get("k10");
        System.out.println("k10 " + v10);

        System.out.println("contains k3 " + simpleHashMap.containsKey("k3"));

        simpleHashMap.remove("k9");
        System.out.println("contains k9 " + simpleHashMap.containsKey("k9"));

        simpleHashMap.remove("k14");
        System.out.println("contains k14 " + simpleHashMap.containsKey("k14"));

        String v22 = simpleHashMap.get("k22");
        System.out.println("k22 " + v22);


        System.out.println(simpleHashMap.size());
    }
}


class SimpleHashMap<K, V> {
    private KV[] array;
    private int size;

    public SimpleHashMap() {
        this.array = new KV[16];
    }

    public void put(K key, V value) {
        if (key == null)
            throw new IllegalArgumentException("key null");

        if (size >= array.length * 0.75) {
            rehash();
        }

        KV kv = new KV(key, value);
        int index = indexFor(key);
        KV old = array[index];
        if (old == null) {
            array[index] = kv;
        } else {
            old.next = kv;
        }
        size++;
    }

    public V get(K key) {
        int index = indexFor(key);
        KV kv = array[index];
        while (kv != null && !kv.key.equals(key)) {
            kv = kv.next;
        }
        if (kv == null)
            return null;
        else
            return (V) kv.value;
    }

    public void remove(K key) {
        int index = indexFor(key);
        KV kv = array[index];
        KV pre = null;
        while (kv != null && !kv.key.equals(key)) {
            pre = kv;
            kv = kv.next;
        }
        if (kv != null) {
            if (pre != null)
                pre.next = kv.next;
            else if (kv.next != null) {
                array[index] = kv.next;
            } else
                array[index] = null;

        }
    }

    public void rehash() {
        System.out.println("rehash");
        KV[] tmpArray = new KV[array.length * 2];
        for (KV tmp : array) {
            KV kv = tmp;
            while (kv != null) {


                KV next = kv.next;


                // re put
                kv.next = null;
                int index = indexFor((K) kv.key);
                KV old = tmpArray[index];
                if (old != null) {
                    old.next = kv;
                } else {
                    tmpArray[index] = kv;
                }


                kv = next;
            }
        }

        array = tmpArray;
    }

    public boolean containsKey(K key) {
        int index = indexFor(key);
        KV kv = array[index];
        while (kv != null && !kv.key.equals(key)) {
            kv = kv.next;
        }
        if (kv == null)
            return false;
        else
            return true;
    }

    public boolean containsValue(V value) {
        if (value == null)
            return false;
        for (KV tmp : array) {
            KV kv = tmp;
            while (kv != null) {
                if (value.equals(kv.value))
                    return true;
            }
        }
        return false;
    }

    public int size() {
        return size;
    }

    private int indexFor(K key) {
        return key.hashCode() % array.length;
    }

    static class KV<K, V> {
        private K key;
        private V value;
        private KV next;

        public KV(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }

        K key() {
            return this.key;
        }

        void key(K key) {
            this.key = key;
        }

        V value() {
            return this.value;
        }

        void value(V value) {
            this.value = value;
        }

        KV next() {
            return this.next;
        }

        void next(KV next) {
            this.next = next;
        }
    }


}
